package main

import "fmt"

// 316. 去除重复字母
// 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。
// 需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

// 问题：字典序？  字符序号

// 栈
type Elem rune

type Stack struct {
	Data   []Elem
	Length int
}

func (sk *Stack) Contains(e Elem) bool {
	for i := 0; i < sk.Length; i++ {
		if sk.Data[i] == e {
			return true
		}
	}
	return false
}
func (sk *Stack) IsEmpty() bool {
	return sk.Length == 0
}
func (sk *Stack) Peek() Elem {
	return sk.Data[sk.Length-1]
}

func (sk *Stack) IndexOf(e Elem, startIdx int) int {
	for i := startIdx + 1; i < sk.Length; i++ {
		if sk.Data[i] == e {
			return i
		}
	}
	return -1
}
func (sk *Stack) Pop() {
	if sk.Length == 0 {
		return
	}
	sk.Data = sk.Data[:sk.Length-1]
	sk.Length = sk.Length - 1
}
func (sk *Stack) Push(e Elem) {
	sk.Data = append(sk.Data, e)
	sk.Length += 1
}
func removeDuplicateLetters(s string) string {

	sk := Stack{Data: []Elem{}, Length: 0}

	for i, ch := range s {
		// ch是新字符，如果比栈顶小，并且后面没有和栈顶一样的，栈顶弹出
		if sk.Contains(Elem(ch)) {
			continue
		}
		for !sk.IsEmpty() && sk.Peek() > Elem(ch) && sk.IndexOf(sk.Peek(), i) != -1 {
			fmt.Println(sk.IsEmpty(), sk.Peek(), ch, sk.IndexOf(sk.Peek(), i))
			sk.Pop()
		}
		sk.Push(Elem(ch))
	}
	bs := []byte{}
	for _, ch := range sk.Data {
		bs = append(bs, byte(ch))
	}
	return string(bs)
}

func main() {
	s := "bcabc"
	res := removeDuplicateLetters(s)
	fmt.Println(res)
}
